package leetcode;
/**
 * 543.二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点
 */
public class Num_543 {
    private int max = 0; //最大直径
    public int diameterOfBinaryTree(TreeNode root) {
        //边界
        if(root == null || (root.left == null && root.right == null)){
            //空节点或只有一个节点
            return 0;
        }
        height(root);
        return max;
    }
    /** 返回该二叉树的最大深度,并且更新最大路径 **/
    private int height(TreeNode root) {
        if(root == null){
            return 0;
        }
        //左子树的深度
        int left = height(root.left);
        //右子树的深度
        int right = height(root.right);
        //更新最大路径
        max = Math.max(max,left + right);
        return 1 + Math.max(left, right);
    }
}
